#include <iostream>
using namespace std;

void quickSort(int* nums, int left, int right){
    if(left >= right) return;
    int i = left;
    int j = right;
    int r = rand() % (right - left + 1) + left;
    swap(nums[left], nums[r]);
    while(i < j){
        while(nums[j] > nums[left] && i < j) j--;
        while(nums[i] <= nums[left] && i < j) i++;
        if(i < j) swap(nums[i], nums[j]);
    }
    swap(nums[left], nums[j]);
    quickSort(nums, left, j-1);
    quickSort(nums, j+1, right);
}

int main(){


    return 0;
}